/*
 **********************************************************
 *
 * Programme : graphes.c
 * ecrit par : Clément HOSOTTE, Jean-Baptiste FUSS
 *
 * resume : fichier source contenant des fonctions utiles
 * à la manipulation des graphes.
 *
 *
 * date : 29/09/2014
 *
 *
 ***********************************************************
 */

#include <stdlib.h>
#include "graphes.h"
#include <stdio.h>
#include <string.h>
#define TAILLE_MAX 1000


/*
 * Fonction : creation
 *
 * Parametres :
 * int nbMaxSommets: un entier représentant le nombre maximal de sommets
 *
 * Retour : un pointeur sur une structure TypGraphe
 *
 * Description : Fonction qui créé une structure de type graphe 
 * et l'alloue en mémoire.
 *
 */
TypGraphe* creationGraphe(int nbMaxSommets, int estOriente){
    int i = 0;
    
    /*
     * Detection d'une mauvaise entree de l'orientation du graphe
     * ou d'une saisie d'un nombre négatif de sommets
     */
    if ((estOriente != 0 && estOriente != 1) || nbMaxSommets <= 0){
        return NULL;
    }
    TypGraphe *g = (TypGraphe*) malloc(sizeof(TypGraphe));
    g->estOriente = estOriente;
    g->nbMaxSommets = nbMaxSommets;
    /* Allocation mémoire du tableau de type TypVoisins*/
    g->listesAdjacences = (TypVoisins**) malloc(g->nbMaxSommets * sizeof(TypVoisins*));
    /*Initialisation du graphe*/
    for (i;i<nbMaxSommets;i++){
        g->listesAdjacences[i] = NULL;
    }
    return g;
}

/*
 * Fonction : lecture
 *
 * Parametres :
 * char nom_fichier[] : une chaine de caractères représentant le nom du fichier 
 * à lire
 *
 * Retour : un pointeur sur une structure TypGraphe
 *
 * Description : Fonction qui créé une structure de type graphe 
 * par rapport au contenu d'un fichier text.
 *
 */
TypGraphe* lecture(char *nom_fichier){
    FILE* fichier = NULL;
    int nbMaxSommet; 			/* Le nombre maximal de sommets dans le graphe*/
    char estOriente = -1;		/* Graphe orienté ou non*/
    int num_ligne = 0;			/* Le numéro de la ligne lue*/
    int curseur_ligne;			/* La position du curseur sur le ligne lue*/
    char ligne_lue[TAILLE_MAX];
    int sommetOrigine;			/* Sommet servant pour insertion*/
    int sommetDestination;		/* Sommet servant pour insertion*/
   	int ponderation;			/* Pondération*/
   	char *chaineDecomposee;		/* Chaîne servant à découper les sommets voisins*/
   	char *sousChaineDecomposee;	/* Chaîne servant à séparer les (s/d)*/
   	char *indice;	
    TypGraphe *g = NULL;
   
    fichier = fopen(nom_fichier, "r");   
   	/*
     * La première étape consiste à lire un fichier et intilialiser un graphe
     * à partir de son orientation et du nombre de sommets maximum.
     * La deuxième étape consiste à ajouter des sommets au graphe ainsi 
     * que ses arêtes.
     */
    if (fichier != NULL) {
        //On lit chaque ligne du fichier
        while (fgets(ligne_lue, TAILLE_MAX, fichier) != NULL) {
        	curseur_ligne = 0;
        	/* Suppression des espaces en début de fichier*/
        	while (ligne_lue[curseur_ligne] == 32 || ligne_lue[curseur_ligne] == 9) {
        		curseur_ligne ++;
        	}
        	/* Instructions prises en compte à partir du numéro de ligne*/
        	switch (num_ligne) {
        		case 1 : 
        			nbMaxSommet = (int) strtol(ligne_lue, NULL, 10);
        			break;
        		case 3 :
        			if (ligne_lue[curseur_ligne] == 'n' || ligne_lue[curseur_ligne] == 'N') {
        				estOriente = 0;
        			}
        			else if (ligne_lue[curseur_ligne] == 'o' || ligne_lue[curseur_ligne] == 'O') {
        				estOriente = 1;
        			}
        			/* 
        			* Avec la troisième ligne, 
        			* toutes les infos sont disponibles 
        			* pour instancier le graphe
        			*/
        			g = creationGraphe(nbMaxSommet,estOriente);
        			break;
        		default :
        			/* On ne veut pas traiter les lignes commençant par #*/
        			if (ligne_lue[curseur_ligne] != '#') {
        				/* Traitement des sommets et arêtes*/
        				chaineDecomposee =  strtok(ligne_lue,":");
        				sommetOrigine = atoi(ligne_lue);
        				insertionSommet(g,sommetOrigine);
        				chaineDecomposee = strtok(NULL,"/");
        				/* Parcours des duo (s/p)*/
        				while (chaineDecomposee != NULL) {
        					sommetDestination = -1;
        					ponderation = -1;
        					/* 
        					* Decoupage de la chaîne 
        					* pour différencier le sommet destination
        					* de la pondération
        					*/
        					/* Suppression de l'occurence de ( pour que atoi fonctionne*/
        					indice = (char*) memchr(chaineDecomposee,'(',strlen(chaineDecomposee));
        					if (indice != NULL) {
        						chaineDecomposee[indice-chaineDecomposee] = 9;
        						sommetDestination = atoi(chaineDecomposee);
        					}
        					chaineDecomposee = strtok(NULL,",");
        					ponderation = atoi(chaineDecomposee);
        			 		/* Vérification que les données ont bien été reçues*/
        					if (ponderation != -1 && sommetDestination != -1) {
        						/* Insertion du sommet comme il n'a pas encore été lu*/
        						insertionSommet(g,sommetDestination);	
        						creationArete(g,sommetOrigine,sommetDestination,ponderation);
        					}
        					/* On passe au duo (s/p) suivant*/
        					chaineDecomposee = strtok(NULL,"/");
        				}
        			}
        			break;
        	}
        	num_ligne++;
		}
		fclose(fichier);
    }
    else {
        printf("Impossible d'ouvrir le fichier\n");
    }
    return g;
}

/*
 * Fonction : insertionSommet
 *
 * Parametres :
 * TypGraphe *g : Le graphe auquel on ajoute un sommet
 * int sommet : Le sommet à ajouter au graphe
 *
 * Retour : 1 si l'insertion s'est correctement effectuée,
 * -1 si le sommet est > au nbMaxSommets
 * et -2 si le sommet existe déjà
 *
 * Description : Fonction qui ajoute un sommet à un graphe
 * (c'est à dire ajoute un sommet fictif -1 à la position sommet 
 * du tableau de listes d'adjacences)
 *
 */
int insertionSommet(TypGraphe *g, int sommet){
    /* Détection du cas d'erreur, c.a.d si le sommet n'est pas compris dans le graphe*/
    if (sommet > g->nbMaxSommets || sommet < 1){
        return -1;
    }
    /* Détection du cas d'erreur lorsque le sommet existe déjà*/
    if (g->listesAdjacences[sommet - 1] == NULL){
        TypVoisins *firstElem = ajouterEnTete(g->listesAdjacences[sommet - 1],-1,0);
        g->listesAdjacences[sommet - 1] = firstElem;
        return 1;
    }
    else {
        return -2;
    }
    
}

/*
 * Fonction : affichage
 *
 * Parametres :
 * TypGraphe *g : Le graphe que l'on veut afficher
 *
 * Retour : void
 *
 * Description : Fonction qui affiche un graphe selon le format obligatoire
 *
 */
void affichage(TypGraphe *g){
    int nb = g->nbMaxSommets;
    int i = 0;
    
    printf("# Nombre maximum de sommets dans le graphe\n");
    printf("%d\n",nb);
    printf("# Oriente\n");
    if (g->estOriente == 0){
        printf("n\n");
    }
    else if (g->estOriente == 1){
        printf("o\n");
    }
    printf("# sommets : voisins\n");
    
    /* On parcours le tableau de listes d'adjacences*/
    for (i; i < nb; i++){
        /* Check si le sommet appartient au graphe*/
        if (g->listesAdjacences[i] != NULL){
            printf("%d : ",i+1);
            afficherListe(g->listesAdjacences[i]);
            printf("\n");
        }
    }
}

/*
 * Fonction : creationArete
 *
 * Parametres :
 * TypGraphe *g : Le graphe auquel on veut ajouter une arête
 * int sommetOrigine : le sommet d'où part l'arête
 * int sommetDestination : le sommet où arrive l'arête
 * int ponderation : la valeur pondérée de l'arête
 *
 * Retour : void
 
 * Description : Fonction qui ajoute une arête dans un graphe entre 2 sommets
 *
 */
void creationArete(TypGraphe *g, int sommetOrigine, int sommetDestination, int ponderation){
    TypVoisins *firstElem;
    
    //On verifie si l'arrête origine -> destination existe pas (sinon pas besoin de la créer)
    if (estDansListe(g->listesAdjacences[sommetOrigine - 1], sommetDestination) == 0){
        firstElem = ajouterEnTete(g->listesAdjacences[sommetOrigine - 1], sommetDestination, ponderation);
        /* On fait pointer le premier élément de la liste vers le nouvel élément*/
        g->listesAdjacences[sommetOrigine - 1] = firstElem;
        printf("Insertion d'une arête (%d,%d)\n",sommetOrigine,sommetDestination);
    }
    else {
        printf("L'arête (%d,%d) existe déjà\n",sommetOrigine,sommetDestination);
    }
}

/*
 * Fonction : verificationsAvantInsertionArete
 *
 * Parametres :
 * TypGraphe *g : Le graphe auquel on veut ajouter une arête
 * int sommetOrigine : le sommet d'où part l'arête
 * int sommetDestination : le sommet où arrive l'arête
 *
 * Retour : -1 si le sommet d'origine n'est pas compris dans le graphe
 * -2 si le sommet destination n'est pas compris dans le graphe
 * -3 si le sommet origine n'est pas initialisé
 * -4 si le sommet destination n'est pas initialisé
 * 1 si toutes les conditions sont remplies
 
 * Description : Fonction qui contrôle le graphe avant
 * de pouvoir ajouter une arête entre deux sommets
 *
 */
int verificationsAvantInsertionArete(TypGraphe *g, int sommetOrigine, int sommetDestination){
	 char c;
	 
	 /* Détection des cas d'erreur, si le sommet d'origine et le sommet destination
     sont compris dans le graphe*/
    if (sommetOrigine > g->nbMaxSommets || sommetOrigine < 1) {
        return -1;
    }
    if (sommetDestination > g->nbMaxSommets || sommetDestination < 1) {
        return -2;
    }
	/* Si le sommet d'origine n'existe pas*/
    if (g->listesAdjacences[sommetOrigine - 1] == NULL) {
        /* On propose à l'utilisateur de le créer*/
        printf("\n>>Le sommet %d n'existe pas, voulez-vous le créer ? (y/n)\n",sommetOrigine);
        c = getchar();
        //On compare la valeur du caractère reçu (Y,y,N,n)
        while (c != 89 && c != 121 && c != 78 && c != 110){
            /* vidange du flux */
            while (getchar() != '\n');
            printf("Erreur lors de la saisie, les deux options sont y(yes) et n(no)\n");
            c = getchar();
        }
        if (c == 89 || c == 121){
        	insertionSommet(g, sommetOrigine);
            printf("Insertion du sommet %d \n",sommetOrigine);
        }
        /* Si le sommet n'est pas créer, alors renvoie d'une erreur*/
        else {
        	return -3;
        }
        /* vidange du flux */
        while(getchar() != '\n');
    }
    // Si le sommet d'originie existe mais pas le sommet destination
    if (g->listesAdjacences[sommetDestination - 1] == NULL && g->listesAdjacences[sommetOrigine - 1] != NULL) {
        /* On propose à l'utilisateur de le créer*/
        printf("\n>>Le sommet %d n'existe pas, voulez-vous le créer ? (y/n)\n",sommetDestination);
        c = getchar();
        //On compare la valeur du caractère reçu (Y,y,N,n)
        while (c != 89 && c != 121 && c != 78 && c != 110){
            /* vidange du flux */
            while (getchar() != '\n');
            printf("Erreur lors de la saisie, les deux options sont y(yes) et n(no)\n");
            c = getchar();
        }
        if (c == 89 || c == 121){
            insertionSommet(g, sommetDestination);
            printf("Insertion du sommet %d \n",sommetDestination);
        }
        /* Si le sommet n'est pas créer, alors renvoie d'une erreur*/
        else {
        	return -4;
        }
        /* vidange du flux */
        while(getchar() != '\n');
    }
    return 1;
}

/*
 * Fonction : insertionArete
 *
 * Parametres :
 * TypGraphe *g : Le graphe auquel on veut ajouter une arête
 * int sommetOrigine : le sommet d'où part l'arête
 * int sommetDestination : le sommet où arrive l'arête
 * int ponderation : la valeur pondérée de l'arête
 *
 * Retour : la valeur retournée par la fonction 
 * verificationsAvantInsertionArete en cas d'erreur
 * 1 en cas de succès
 
 * Description : Fonction qui contrôle le graphe avant 
 * d'ajouter une arête entre deux sommets
 *
 */
int insertionArete(TypGraphe *g, int sommetOrigine, int sommetDestination, int ponderation){
	/* Vérifications des pré-requis avant d'aller plus loin*/ 
	int conditions = verificationsAvantInsertionArete(g, sommetOrigine, sommetDestination);
	if (conditions != 1) {
	   	return conditions;
	}
    /* On différencie les cas d'un graphe orienté ou non*/
    if (g->estOriente == 0){ /* S'il ne l'est pas*/
        /* Création de la 1ère arête*/
        creationArete(g, sommetOrigine, sommetDestination, ponderation);
        /* Création de la 2ème arête*/
        creationArete(g, sommetDestination, sommetOrigine, ponderation);
    }
    else if (g->estOriente == 1){
        char c;
        printf("Voulez-vous créer l'arête symétrique (%d,%d)? (y/n)\n",sommetDestination,sommetOrigine);
        c = getchar();
        //On compare la valeur du caractère reçu (Y,y,N,n)
        while (c != 89 && c != 121 && c != 78 && c != 110){
            /* vidange du flux */
            while (getchar() != '\n');
            printf("Erreur lors de la saisie, les deux options sont y(yes) et n(no)\n");
            c = getchar();
        }
        creationArete(g, sommetOrigine, sommetDestination, ponderation);
        /* Création de l'arête symétrique*/
        if (c == 89 || c == 121){
            creationArete(g, sommetDestination, sommetOrigine, ponderation);
        }
        /* vidange du flux */
        while(getchar() != '\n');
    }
    
    return 1;
}

/*
 * Fonction : supprimerArete
 *
 * Parametres :
 * TypGraphe *g : Le graphe auquel on veut ajouter une arête
 * int sommetOrigine : le sommet d'où part l'arête
 * int sommetDestination : le sommet où arrive l'arête
 *
 * Retour : 1 si le voisin a été supprimé, 0 s'il n'était pas dans la liste
 
 * Description : Fonction qui supprime une arête dans un graphe entre 2 sommets
 *
 */
int supprimerArete(TypGraphe *g, int sommetOrigine, int sommetDestination){
	/* Vérification que l'élément est présent dans la liste*/
	if (estDansListe(g->listesAdjacences[sommetOrigine-1], sommetDestination) == 1) {
		TypVoisins *v = supprimerElement(g->listesAdjacences[sommetOrigine-1], sommetDestination);
		/* On réindexe la liste dans le cas où l'élément supprimé était en tête de file*/
		if (v != NULL) {
			g->listesAdjacences[sommetOrigine-1] = v;
		}
		/* Si le graphe n'est pas orienté, on supprime l'ârete inverse*/
		if (g->estOriente == 0){
			v = supprimerElement(g->listesAdjacences[sommetDestination-1], sommetOrigine);
			if (v != NULL) {
				g->listesAdjacences[sommetDestination-1] = v;
			}
		} 
		return 1;
	}
	return -1;
}

/*
 * Fonction : supprimerSommet
 *
 * Parametres :
 * TypGraphe *g : Le graphe auquel on veut supprimer un sommet
 * int sommet: la valeur du sommet à supprimer
 *
 * Retour : 1 si le somemt est supprimé, -1 s'il n'appartenait pas au graphe
 
 * Description : Fonction qui libère la mémoire d'un sommet dans le graphe
 *
 */
int supprimerSommet(TypGraphe *g, int sommet){
	/* Détection d'erreur: On vérifie que le sommet à supprimer appartient au graphe*/
	if (sommet > g->nbMaxSommets || sommet < 1) {
        return -1;
    }
    if (g->listesAdjacences[sommet - 1] == NULL) {
    	return -2;
    }
    TypVoisins *firstElem;
    firstElem = effacerListe(g->listesAdjacences[sommet - 1]);
	g->listesAdjacences[sommet - 1] = firstElem;
	return 1;
}

/*
 * Fonction : quitter
 *
 * Parametres :
 * TypGraphe **g : un pointeur sur le graphe que l'on veut supprimer 
 * de la mémoire avant de quitter
 *
 * Retour : void
 
 * Description : Fonction qui libère la mémoire avant de fermer le programme
 *
 */
void quitter(TypGraphe **g){
    if (*g != NULL) {
		int i = 0;
		/* Suppression des listes d'adjacences*/
		for (i; i < (*g)->nbMaxSommets; i++){
		    TypVoisins *firstElem;
		    firstElem = effacerListe((*g)->listesAdjacences[i]);
		    /* On fait pointer le premier élémént de la liste sur NULL 
		    * (renvoyé par la fonction effacerListe)
		    */
		    (*g)->listesAdjacences[i] = firstElem;
		    free(firstElem);
		}
		free((*g)->listesAdjacences);
		free(*g);
		/* On remet la valeur NULL (car free ne le fait pas)*/
		*g = NULL;
    }
}

/*
 * Fonction : sauverGraphe
 *
 * Parametres :
 * TypGraphe *g : le graphe que l'on veut sauvegarder dans un fichier texte
 * char *nomFich : le nom du fichier où le graphe est sauvé
 *
 * Retour : 1 si le fichier a pu être ouvert, -1 sinon
 
 * Description : Fonction qui permet de sauvegarder un graphe 
 * dans un fichier texte
 *
 */
int sauverGraphe(TypGraphe *g, char *nomFich){
	FILE* fichier = NULL;
	TypVoisins *courant;
	int i = 0;
	
    fichier = fopen(nomFich, "w");
 	/* Le traitement se fait si le fichier a pu être ouvert*/
    if (fichier != NULL)
    {
        // On l'écrit dans le fichier
        fprintf(fichier, "# nombre maximal de sommets\n");
        fprintf(fichier, "%d\n", g->nbMaxSommets);
        fprintf(fichier, "# oriente\n");
        // check si le graphe est orienté ou non
        if (g->estOriente == 0) {
        	fprintf(fichier,"n\n");
        }
        else {
        	fprintf(fichier,"o\n");
        }
        fprintf(fichier,"# sommets : voisins\n");
        // Parcours des sommets du graphe
        for (i; i < g->nbMaxSommets; i++) {
        	// On ne veut que les sommets initialisé
        	if (g->listesAdjacences[i] != NULL) {
        		fprintf(fichier, "%d : ", i+1);
        		courant = g->listesAdjacences[i];
        		// Parcours de la liste d'adjacence
        		while (courant->voisin != -1) {
        			fprintf(fichier, "(%d/%d)", courant->voisin, courant->ponderation);
        			courant = courant->voisinSuivant;
        			if (courant->voisin != -1) {
        				fprintf(fichier,", ");
        			}
        		}
        		fprintf(fichier, "\n");
        	}
        }
        // Fermeture du pointeur sur le fichier
        fclose(fichier);
        return 1;
    }
    else {
    	return -1;
    }

}


